#include<stdio.h> 
#include<malloc.h>

#define MAXSIZE 100
#define m 8 
#define n 8 

typedef struct
{
    int x, y, d;
} Point;

typedef struct
{
    Point data[MAXSIZE];
    int top;
} MazeStack;

typedef struct
{
    int x, y;
} Item;

void SetNULL(MazeStack *s) 
{ 
    s->top = -1; 
}

int IsEmpty(MazeStack *s)
{
    if (s->top >= 0)
        return 0;
    else
        return 1;
}

MazeStack *Push(MazeStack *s, Point x)
{
    if (s->top > MAXSIZE - 1)
    {
        printf("overflow!\n");
        return s;
    }
    else
    {
        s->top++;
        s->data[s->top] = x;
        return s;
    }
}
Point *Pop(MazeStack *s)
{
    if (IsEmpty(s))
    {
        printf("empty!\n");
        return NULL;
    }
    else
    {
        s->top--;
        return &(s->data[s->top + 1]);
    }
}
Point * GetTop(MazeStack *s)
{
    if (IsEmpty(s))
    {
        printf("empty!\n");
        return NULL;
    }
    else
    {
        return &(s->data[s->top]);
    }
}
void DefineMove(Item xmove[8])
{
    xmove[0].x = 0, xmove[0].y = 1;
    xmove[1].x = 1, xmove[1].y = 1;
    xmove[2].x = 1, xmove[2].y = 0;
    xmove[3].x = 1, xmove[3].y = -1;
    xmove[4].x = 0, xmove[4].y = -1;
    xmove[5].x = -1, xmove[5].y = -1;
    xmove[6].x = 1, xmove[6].y = 0;
    xmove[7].x = -1, xmove[7].y = 1;
}
int main()
{
    int maze[10][10] = {
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
    {-1, 0, 0,-1, 0, 0, 0,-1, 0,-1},
    {-1, 0, 0,-1, 0, 0, 0,-1, 0,-1},
    {-1, 0, 0, 0, 0,-1,-1, 0, 0,-1},
    {-1, 0,-1,-1,-1, 0, 0, 0, 0,-1},
    {-1, 0, 0, 0,-1, 0, 0, 0, 0,-1},
    { 1, 0, 1, 0, 0, 0, 1, 0, 0,-1},
    {-1, 0,-1,-1,-1, 0,-1,-1, 0,-1},
    {-1,-1, 0, 0, 0, 0, 0, 0, 0,-1},
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
};

    int x = 0;
    int y = 0;
    int i = 0;
    int j = 0;
    int d = 0;
    Item xmove[8];
    Point start;
    Point *p;
    MazeStack *s;
    s = (MazeStack *)malloc(sizeof(MazeStack));
    SetNULL(s);
    DefineMove(xmove);
    // printf("enter your own maze : \n");
    // for (i = 0; i < m + 2; i++)
    //     for (j = 0; j < n + 2; j++)
    //         scanf("%d", &maze[i][j]);
    start.x = 1;
    start.y = 1;
    start.d = -1;
    p = (Point *)malloc(sizeof(Point));
    s = Push(s, start);
    while (!IsEmpty(s))
    {
        p = Pop(s);
        x = p->x;
        y = p->y;
        d = p->d + 1;
        while (d < 8)
        {
            i = xmove[d].x + x;
            j = xmove[d].y + y;
            if (maze[i][j] == 0)
            {
                p->d = d;
                s = Push(s, *p);
                x = i;
                y = j;
                maze[x][y] = -1;
                Point nw;
                nw.x = x;
                nw.y = y;
                nw.d = -1;
                s = Push(s, nw);
                if (x == m && y == n)
                {
                    printf("a safe path is : \n");
                    while (!IsEmpty(s))
                    {
                        p = Pop(s);
                        printf("(%d,%2d,%2d)\n", p->x, p->y, p->d);
                    }
                    return 1;
                }
                else
                {
                    break;
                }
            }
            else
            {
                d++;
            }
        }
    }
    getchar();
    getchar();
    return 0;
}
